package com.longge;

public class PreBuildTree {


    public TreeNode buildTree(int[] preorder, int[] inorder) {

        int val = preorder[0];
        TreeNode root = new TreeNode(val);
        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                index = i;
                break;
            }
        }
        int leftSize = preorder.length - 1 - index;
        root.left = buildSubTree(preorder, 1, 1 + leftSize, inorder, 0, index - 1);
        root.right = buildSubTree(preorder, 1 + leftSize, preorder.length - 1, inorder, index + 1, inorder.length - 1);
        return root;
    }

    private TreeNode buildSubTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inoStart, int inoEnd) {
        if (preStart > preEnd) return null;
        int val = preorder[preStart];
        TreeNode root = new TreeNode(val);
        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                index = i;
                break;
            }
        }
        int leftSize = preorder.length - 1 - index;
        root.left = buildSubTree(preorder, preStart, preStart + leftSize, inorder, inoStart, index - 1);
        root.right = buildSubTree(preorder, preStart + leftSize, preEnd, inorder, index + 1, inoEnd);
        return root;

    }

}
